本篇為 MIT 6.0001 Introduction to Computer Science and Programming in Python 心得

What is Recursion
演算法: 將問題分解成簡單的小問題來解決
語義解釋：一種function call itself 的手法，有三個條件 1. 不能構成無窮迴圈、2. 需有至少一個可以簡單解決的base case、3. 需用同一個解決方式解決不同的input。

Iteration v.s. Recursion

Example 1. Multiplication 乘法("多個 a * b" or "a加自己b次")

Iteration

操作 "state" by

• "iteration" 次數 (i) 從b開始： i -> i-1 到 0
• 目前計算結果 result -> result + a

def muti_iter(a, b):
    result = 0
    while b < 0:
        result += a
        b -= 1
    return result

Recursion

原則：將問題簡化成簡單且小的版本來解決。

a*b = (a + a + ..... + a) (b 次)
    = a + (a + a + .... + a) (b - 1次)
    = a + a * (b - 1)

base case: b = 1時 答案為 a

def muti_recu(a, b):
    if b == 1:
        return a
    else:
        return a + muti_recu(a, b-1)

Example 2. Factorial

Iteration

def factorial_iter(n):
    result = 1
    for i in range(1, n-1):
        result *= i
    return result

Recursion

def factorial_recu(n):
    if n == 1:
        return 1
    else:
        return n*factorial_recu(n-1)

scope and binding in Recursion

• 每一個 recursion call to a function 都產生了一個自己的scope/environment
• binding 的變數都沒有被改變 (immutable)
  每一次的recursion的變數雖然都是同一個名稱，但實際上是不同的object